#ifndef VCELLS_H
#define	VCELLS_H

/*               VCells.cpp by Jie Wang (jiewangustc@gmail.com)
 *   This code implements the basic functional of VCells algorithms described 
 *in "VCells: Simple and Efficient Superpixels Using Edge-Weighted Centroidal 
 *Voronoi Tessellations, TPAMI 34(6), 1241-1247" by Jie Wang and Xiaoqiang Wang.
 *The detailed technical discussions can be found in "An edge-weighted centroidal 
 *Voronoi tessellation model for image segmentation, 
 *Image Processing, IEEE Transactions on 18 (8), 1844-1858" by Jie Wang, Lili Ju 
 *and Xiaoqiang Wang. 
 *
 *                      DISCLAIMER:  
 *   This code is for academic (non-commercial) use only.  Moreover, the code 
 *comes with absolutely NO warranty of any kind. I take no responsibility for 
 *the reliability of the results.
 *
 *                      PLATFORM
 *   The code is tested under Visual Studio 2010 with Window 7 OS.
 *
 *                      HOW TO USE THIS CODE
 *   The code currently only supports .bmp files. You can specify the image 
 *file name in the main function. You can adjust the key parameters in lines 
 *43-46. We provide an example image "127.bmp", which is taken from the "Berkeley 
 *Segmentation Dataset", and the corresponding results. By default, we use 
 *the Lab color space. Have fun.
 */


//#include<Windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<iostream>
#include<fstream>
#include<sstream>

#define MAX_RADIUS 9 // 3; the radius of neighborhood when calculating the length energy
#define MAX_NUM_NEI_CLUSTER 400 // 200; the number of neighbor clusters
#define MAX_NUM_DIRECT_NEI 16 // 4

struct pixel {
    
    int indexCluster; // segment label
    int index;// suppose the image has M*N pixels, index is from 0 to M*N - 1
    int row; // the row index, from 0 to M-1
    int column; // the column index, from 0 to N-1
    int directNei[MAX_NUM_DIRECT_NEI]; // at most, a pixel can have 4 direct neighbors
    int numDirectNei; // the number of direct neighbor which is directly connected to the current pixel
    int numNeiPixels;	// number of pixels inside the neighborhood which is defined as a disk, include the current pixel itself
    int numNeiCluster; // number of clusters inside the neighborhood. 
    int neiPixel[(2*MAX_RADIUS+1) * (2*MAX_RADIUS+1)]; // the index of the pixels inside the neighborhood
    int numNeiPixelEachCluster[MAX_NUM_NEI_CLUSTER]; // this array stores the number of pixels inside the neighbor clusters
                                                                                             // the index of the cluster in position i is indexNeiClusters[i]. Only at
                                                                                             // the initialization step, the first 
                                                                                             // position is defaulted to store the number of pixels which belong to the 
                                                                                             // same cluster as the current pixel.
    int indexNeiClusters[MAX_NUM_NEI_CLUSTER]; // this array stores the index of the clusters inside the neighborhood
                                                                               // only at the initialization step, the first position is defaulted to store the cluster index of the current
                                                                               // current pixel. i.e., indexNeiClusters[0] = indexCluster.	
    double color[3];
    bool hitted;
};

struct centroid {
    int index; // the position in the array
    int numPixels; // number of pixels belong to the cluster generated by this generator
    double row;
    double column;
    double color[3];
};

class VCells {
public:
//    int CIELab = 1; // if "1", make use of the Lab color metric; otherwise, use RGB color space 
    
    int NUM_CLUSTER; // the number of segments you want
    double WEIGHT_LENGTH; // the weight parameter of the edge energy
    int RADIUS;
    int NUM_NEI_CLUSTER;
    int NUM_DIRECT_NEI;
    int THRESHOLD;
    
//    unsigned char *pBmpBuf; // pointer to the readin bmp file
    int bmpWidth; // the width of the image (count in pixel)
    int bmpHeight; // the height of the image
    int lineByte;
    int trueNumCluster; // if we use square box to initialize, the true number of clusters may not be 
                                            // exactly the predefined value
    
    VCells() : 
            NUM_CLUSTER(400), WEIGHT_LENGTH(5.0), RADIUS(3), 
            NUM_NEI_CLUSTER(200), NUM_DIRECT_NEI(4), THRESHOLD(10) {
        
    }
    
    VCells(int num_cluster, double weight_length) : 
            NUM_CLUSTER(num_cluster), WEIGHT_LENGTH(weight_length), RADIUS(3), 
            NUM_NEI_CLUSTER(200), NUM_DIRECT_NEI(4), THRESHOLD(10) {
        
    }
    
    VCells(int num_cluster, double weight_length, int radius, int num_nei_cluster, int num_direct_nei, int threshold) : 
            NUM_CLUSTER(num_cluster), WEIGHT_LENGTH(weight_length), RADIUS(radius), 
            NUM_NEI_CLUSTER(num_nei_cluster), NUM_DIRECT_NEI(num_direct_nei), THRESHOLD(threshold) {
        
    }
    
    ~VCells() {
        
    }
    
    /************************************************************************
    *Name of the function:  
    *						int getIndexFromRC(int row, int column)
    *Parameter of the function:
    *		row, column
    *Return Value: 
    *		bmpWidth * row + column
    *Comment: 
    *		given the index of row and column, return the corresponding index
    *		in the whole one array.
    ************************************************************************/
    int getIndexFromRC(int row, int column){
            return bmpWidth * row + column;
    }

    /************************************************************************
    *Name of the function:  
    *						void getRCFromIndex(int index, int* row, int* column)
    *Parameter of the function:
    *		index --- the index of the pixel in the 1d array
    *		row --- the corresponding row index 
    *		column --- the corresponding column index
    *Return Value: 
    *		none
    *Comment: 
    *		given the index calculate the corresponding row, column index
    ************************************************************************/
    void getRCFromIndex(int index, int* row, int* column){
            *row = index / bmpWidth;
            *column = index % bmpWidth;
    }

    /************************************************************************
    *Name of the function:  
    *						bool isOutOfDomain()
    *Parameter of the function:
    *		indexROC --- the row or column index of a pixel
    *		ROC --- indicate whether the index is of row or column
    *Return Value: 
    *		0 the index is within the domain, 1 the index is out of the domain
    *Comment: 
    *		given a row or column index, determine whether this index is out
    *		of the domain
    ************************************************************************/
    bool isOutOfDomain(int indexROC, int ROC){

            if(ROC == 1) // the index is a row index
            {
                    if((indexROC < 0)|| (indexROC >= bmpHeight) ){
                            return true;
                    }else{
                            return false;
                    }
            } 
            else if(ROC ==2) // the index is a column index
            {
                    if((indexROC < 0)||(indexROC >= bmpWidth)){
                            return true;
                    }else{
                            return false;
                    }
            }else{
                    printf("input is not recognizable! please check again!\n");
                    return false;
                    exit(0);
            }


    }


    /********************************************************************************************************/
    /*******                                   Convert RGB to Lab                                     *******/
    /********************************************************************************************************/
    void RGB2Lab(double vec[]){
            int i;
            double index = 0.333333;
            double X, Y, Z, XT, YT, ZT,Y3, fx, fy, fz, inv1, inv2;
            inv1 = 1/0.950456;
            inv2 = 1/1.088754;

            for(i = 0; i < 3; i++){
                    vec[i] = vec[i] / 255;
            }

            X = (0.180423 * vec[0] + 0.357580 * vec[1] + 0.412453 * vec[2]) * inv1;
            Y = 0.072169 * vec[0] + 0.715160 * vec[1] + 0.212671 * vec[2];
            Z = (0.950227 * vec[0] + 0.119193 * vec[1] + 0.019334 * vec[2]) * inv2;

            XT = (X > 0.008856 ? 1 : 0);
            YT = (Y > 0.008856 ? 1 : 0);
            ZT = (Z > 0.008856 ? 1 : 0);

            Y3 = pow(Y, index);

            fx = XT * pow(X, index) + (1 - XT) * (7.787 * X + 0.138);
            fy = YT * Y3 + (1 - YT) * (7.787 * Y + 0.138);
            fz = ZT * pow(Z, index) + (1 - ZT) * (7.787 * Z + 0.138);

            vec[0] = YT * (116 * Y3 -16) + (1 - YT) * (903.3 * Y);
            vec[1] = 500 * (fx - fy);
            vec[2] = 200 * (fy - fz);
    }

    /************************************************************************
    *Name of the function:  
    *						bool initializePixel()
    *Parameter of the function:
    *		none
    *Return Value: 
    *		0 fail, 1 successful
    *Comment: 
    *		declare M*N pixels, setup the neighbor pixel index list
    ************************************************************************/
    bool initializePixel(struct pixel* pixelArray){

            int i,j;
            int numNei = 0;

            // declare a two dimension array which stores row and column index for direct neighbor
            int rcDirectNei[2][MAX_NUM_DIRECT_NEI] = {{-1,0,1,0},{0,1,0,-1}};

            //declare a two dimension array which stores row and column index for neighbor pixels
            //first analyze how many pixels are within the disk

            double dist = 0;
            for(i = - RADIUS; i <= RADIUS; i++){
                    for(j = -RADIUS; j <= RADIUS; j++){
                            dist = sqrt((double)i*i+(double)j*j);
                            if (dist <= RADIUS){
                                    numNei++;
                            }
                    }
            }
            //second, declare dimension array to store the row and column index for the neighbor pixels
            // even index stores the row index, odd for column index
//            int* refNeiRCIndex = (int *) malloc( sizeof(int) * 2 * numNei );
            int* refNeiRCIndex = new int[2*numNei];
            numNei = 0;
            for(i = - RADIUS; i<=RADIUS;i++){
                    for(j = - RADIUS; j <= RADIUS; j++){
                            dist = sqrt((double)i*i+(double)j*j);
                            if(dist <= RADIUS){
                                    refNeiRCIndex[numNei*2] = i;
                                    refNeiRCIndex[numNei*2+1] = j;
                                    numNei++;
                            }
                    }
            }

            int k = 0;
            int neiIndex;
            int rowIndexNei,columnIndexNei;
            int trueNumNei, trueDirectNumNei;
            int index;
            for(i = 0; i < bmpHeight; i++){
                    for(j = 0; j < bmpWidth; j++){
                            index = getIndexFromRC(i,j);
                            pixelArray[index].row = i;
                            pixelArray[index].column = j;
                            pixelArray[index].index = index;
                            pixelArray[index].numNeiPixels = 0;
                            pixelArray[index].hitted = false;
                            trueNumNei = 0;
                            for(k = 0; k < numNei; k++){
                                    rowIndexNei = refNeiRCIndex[k*2]+i;
                                    columnIndexNei = refNeiRCIndex[k*2+1]+j;
                                    if((!isOutOfDomain(rowIndexNei,1))&&(!isOutOfDomain(columnIndexNei,2))){
                                            neiIndex = getIndexFromRC(rowIndexNei,columnIndexNei);
                                            pixelArray[index].neiPixel[trueNumNei] = neiIndex;
                                            trueNumNei++;
                                    }
                            }
                            pixelArray[index].numNeiPixels = trueNumNei;

                            trueDirectNumNei = 0;
                            for (k = 0; k < 4; k++)
                            {
                                    rowIndexNei = rcDirectNei[0][k] + i;
                                    columnIndexNei = rcDirectNei[1][k] + j;
                                    if ((!isOutOfDomain(rowIndexNei,1))&&(!isOutOfDomain(columnIndexNei,2)))
                                    {
                                            neiIndex = getIndexFromRC(rowIndexNei,columnIndexNei);
                                            pixelArray[index].directNei[trueDirectNumNei] = neiIndex;
                                            trueDirectNumNei++;
                                    }
                            }
                            pixelArray[index].numDirectNei = trueDirectNumNei;

                            pixelArray[index].numNeiCluster = 1;	// the cluster which current pixel belongs to is a default neighbor cluster

                            for(k = 0; k < NUM_NEI_CLUSTER; k++){
                                    pixelArray[index].numNeiPixelEachCluster[k] = 0;
                                    pixelArray[index].indexNeiClusters[k] = -1;
                            }

                    }
            }

//            free(refNeiRCIndex); 
            delete[] refNeiRCIndex;
            
            // initialize the color information of each pixel
//            double vec[3]={0., 0., 0.};
//            for(i = 0; i < bmpHeight; i++){
//                    for(j = 0; j < bmpWidth; j++){
//                            index = getIndexFromRC(i,j);
//                            for(k = 0; k < 3; k++){
//                                    vec[k] = (double)*(pBmpBuf + i * lineByte + j * 3 + k);
//                            }
//                            if(CIELab == 1){
//                                    RGB2Lab(vec);
//                            }
//                            for(k = 0; k < 3; k++){
//                                    pixelArray[index].color[k] = vec[k];
//                            }
//                    }
//            }

            return true;
    }


    /************************************************************************
    *Name of the function:  
    *						bool initializeGenerators(struct centroid* generators)
    *Parameter of the function:
    *		generators --- array for the generators
    *Return Value: 
    *		bool 
    *		0 fail, 1 successful
    *Comment: 
    *		initialize the generators, note this function is especially for the 
    *		initialization of the generators for the CVT algorithm
    ************************************************************************/
    bool initializeGenerators(struct centroid* generators, struct pixel* pixelArray){
            //printf("initializing the generators!\n");
            int i,j, k;
            int index;
            int randRow;
            int randColumn;

            int gradius = (int)2*sqrt((double)bmpHeight*bmpWidth/(2*3.1415926*NUM_CLUSTER));
            double dist = 0;
            int numNei = 0;
            for(i = - gradius; i <= gradius; i++){
                    for(j = -gradius; j <= gradius; j++){
                            dist = sqrt((double)i*i+(double)j*j);
                            if (dist <= gradius){
                                    numNei++;
                            }
                    }
            }
//            int* refNeiRCIndex = (int *) malloc( sizeof(int) * 2 * numNei );
            int* refNeiRCIndex = new int[2*numNei];
            numNei = 0;
            for(i = - gradius; i<=gradius;i++){
                    for(j = - gradius; j <= gradius; j++){
                            dist = sqrt((double)i*i+(double)j*j);
                            if(dist <= gradius){
                                    refNeiRCIndex[numNei*2] = i;
                                    refNeiRCIndex[numNei*2+1] = j;
                                    numNei++;
                            }
                    }
            }

            srand(time(NULL));
            int refRow, refColumn;
//            int* tempDist2 = (int *) malloc(sizeof(int) * bmpHeight * bmpWidth);
            int* tempDist2 = new int[bmpHeight*bmpWidth];
            int tempDist;
            for(i = 0; i < NUM_CLUSTER; i++){
                    generators[i].index = i;
                    generators[i].numPixels = 0;
                    randRow = rand()%bmpHeight;
                    randColumn = rand()%bmpWidth;
                    generators[i].row = (double) randRow;
                    generators[i].column = (double) randColumn;
                    generators[i].numPixels = 1;
                    index = getIndexFromRC(randRow,randColumn);
                    for(j = 0; j < 3; j++){
                            generators[i].color[j] = pixelArray[index].color[j];
                            }	

                    for(k = 0; k < numNei; k++){
                            refRow = randRow + refNeiRCIndex[2*k];
                            refColumn = randColumn + refNeiRCIndex[2*k+1];
                            if((!isOutOfDomain(refRow,1))&&(!isOutOfDomain(refColumn,2))){
                                    index = getIndexFromRC(refRow, refColumn);
                                    if(pixelArray[index].hitted == false){
                                            tempDist2[index] = (randRow-refRow)*(randRow-refRow) + (randColumn-refColumn)*(randColumn-refColumn);	
                                            pixelArray[index].indexCluster = i;
                                            pixelArray[index].hitted = true;
                                    }else{
                                            tempDist = (randRow-refRow)*(randRow-refRow) + (randColumn-refColumn)*(randColumn-refColumn);	
                                            if(dist < tempDist2[index]){
                                                    pixelArray[index].indexCluster = i;
                                                    tempDist2[index] = tempDist;
                                            }
                                    }
                            }
                    }

            }
            //printf("generators successfully initialized!\n");
//            free(refNeiRCIndex);
//            free(tempDist2);
            delete[] refNeiRCIndex;
            delete[] tempDist2;
            return true;
    }

    /**************************************************************************************************/
    /*  return the index of generator whose is nearest to the given data, in the physical sense       */
    /*  indicator can have two values, 0 means we are generating the Voronoi region, 1 means we are   */
    /*  generating the classic CVTs.                                                                  */
    /**************************************************************************************************/
    int getNearestGenerator(struct centroid* generators,struct pixel* currentPixel,int indicator){
            int nearestGenerator;
            double euclideanDist2,tempEuclideanDist2;
            int i=0;
            int indexClusterNeiPixel;
            int prow = currentPixel->row;
            int pcolumn = currentPixel->column;
            double grow, gcolumn;
            if(indicator == 0){
                    nearestGenerator = 0;
                    grow = generators[0].row;
                    gcolumn = generators[0].column;
                    euclideanDist2 = (prow - grow)*(prow - grow) + (pcolumn - gcolumn)*(pcolumn - gcolumn);
            }else{
                    indexClusterNeiPixel = currentPixel->indexCluster;
                    nearestGenerator = indexClusterNeiPixel;
                    grow = generators[indexClusterNeiPixel].row;
                    gcolumn = generators[indexClusterNeiPixel].column;
                    euclideanDist2 = (prow - grow)*(prow - grow) + (pcolumn - gcolumn)*(pcolumn - gcolumn);
            }

            if(indicator == 0){
                    for(i = 0; i < NUM_CLUSTER; i++){
                            if(i!=currentPixel->indexCluster){
                                    grow = generators[i].row;
                                    gcolumn = generators[i].column;
                                    tempEuclideanDist2 = (prow - grow)*(prow - grow) + (pcolumn - gcolumn)*(pcolumn - gcolumn);
                                    if (tempEuclideanDist2 < euclideanDist2){
                                            nearestGenerator = i;
                                            euclideanDist2 = tempEuclideanDist2;
                                    }
                            }
                    }
            }else{
                    for(i = 0; i < currentPixel->numNeiCluster; i++){
                            if(i!=currentPixel->indexCluster){
                                    if(currentPixel->numNeiPixelEachCluster[i]!=0){
                                            indexClusterNeiPixel = currentPixel->indexNeiClusters[i];
                                            grow = generators[indexClusterNeiPixel].row;
                                            gcolumn = generators[indexClusterNeiPixel].column;
                                            tempEuclideanDist2 = (prow - grow)*(prow - grow) + (pcolumn - gcolumn)*(pcolumn - gcolumn);
                                            if (tempEuclideanDist2 < euclideanDist2){
                                                    nearestGenerator = indexClusterNeiPixel;
                                                    euclideanDist2 = tempEuclideanDist2;
                                            }
                                    }
                            }
                    }
            }

            return nearestGenerator;
    }
    /********************************************************************************************************/
    /*  update the generators once there is data transfer occurs, 1 means the data comes in, 0 means go out */
    /********************************************************************************************************/
    bool updateGenerator(struct centroid* currentGenerator, struct pixel* currentPixel, int IO){

            int i;

            if(IO == 1){
                    currentGenerator->row = (double)currentGenerator->row*currentGenerator->numPixels/(currentGenerator->numPixels+1)+(double)currentPixel->row/(currentGenerator->numPixels+1);
                    currentGenerator->column = (double)currentGenerator->column*currentGenerator->numPixels/(currentGenerator->numPixels+1)+(double)currentPixel->column/(currentGenerator->numPixels+1);
                    for(i = 0; i < 3; i++){
                            currentGenerator->color[i] = currentGenerator->color[i]*currentGenerator->numPixels/(currentGenerator->numPixels+1)+ currentPixel->color[i]/(currentGenerator->numPixels+1);
                    }
                    currentGenerator->numPixels++;
                    return true;
            }
            else if(IO == 0){
                    if(currentGenerator->numPixels > 1){
                            currentGenerator->row = (double)currentGenerator->row*currentGenerator->numPixels/(currentGenerator->numPixels-1)-(double)currentPixel->row/(currentGenerator->numPixels-1);
                            currentGenerator->column = (double)currentGenerator->column*currentGenerator->numPixels/(currentGenerator->numPixels-1)-(double)currentPixel->column/(currentGenerator->numPixels-1);
                            for(i = 0; i < 3; i++){
                                    currentGenerator->color[i] = currentGenerator->color[i]*currentGenerator->numPixels/(currentGenerator->numPixels-1) - currentPixel->color[i]/(currentGenerator->numPixels-1);
                            }
                            currentGenerator->numPixels--;
                            return true;
                    }else{
                            //printf("cluster %d will disappear!\n", currentGenerator->index);
                            currentGenerator->column = -1;
                            currentGenerator->row = -1;
                            currentGenerator->numPixels = 0;
                            for(int k = 0; k < 3; k++){
                                    currentGenerator->color[k] = 0;
                            }
                            return false;
                    }
            }
            else{
                    return false;
            }
    }
    /***********************************************************************************/
    /*  generate the Voronoi region given a set of generators, in the physical sense   */
    /***********************************************************************************/
    bool VoronoiRegion(struct centroid* generators, struct pixel* pixelArray){
            //printf("generating the Voronoi region according to the given generators!\n");
            int i;
            int indexCluster;
            for(i = 0; i < bmpWidth * bmpHeight; i++){
                    if(pixelArray[i].hitted == false){
                            indexCluster= getNearestGenerator(generators,&pixelArray[i],0);
                            pixelArray[i].indexCluster = indexCluster;
                    }else{
                            indexCluster = pixelArray[i].indexCluster;
                    }
                    pixelArray[i].indexNeiClusters[0] = indexCluster;
                    pixelArray[i].numNeiPixelEachCluster[0] = 1;
                    updateGenerator(&generators[indexCluster],&pixelArray[i],1);
            }
            //printf("Voronoi region is generated!\n");

            for (i = 0; i < NUM_CLUSTER; i++)
            {
                    generators[i].numPixels--;
            }

            return true;
    }

    /************************************************************************
    *Name of the function:  
    *				bool isCounted(struct pixel* currentPixel, int indexClusterNeiPixel)
    *Parameter of the function
    *				currentPixel --- currentPixel in hand
    *				indexClusterNeiPixel --- the index of cluster which the neighbor pixel belongs to
    *				position --- this value will store the position where we put the new cluster in indexNeiClusters array.
    *Return Value: 
    *				if there is neighbor pixels wihch belong to the same cluster as the current neighbor
    *				pixel, return true, otherwise, return false
    *Comment: 
    *		search the neighbor pixels for every pixel, record the number of pixels
    *		inside each cluster. 
    ************************************************************************/
    bool isCounted(struct pixel* currentPixel, int indexClusterNeiPixel,int* position){
            int i;
            bool counted = false;
            int numNeiCluster;
            for(i = 0; i < currentPixel->numNeiCluster; i++){
                    if(currentPixel->indexNeiClusters[i] == indexClusterNeiPixel){
                            counted = true;
                            currentPixel->numNeiPixelEachCluster[i]++;
                            *position = i;
                            break;
                    }
            }
            if(counted == false){
                    currentPixel->numNeiCluster++;
                    numNeiCluster = currentPixel->numNeiCluster;
                    if(numNeiCluster>=NUM_NEI_CLUSTER){
                            printf("Warning! the predefined number of neighbor clusters is not OK!\n");
                            exit(0);
                    }else{
                            currentPixel->indexNeiClusters[numNeiCluster-1]=indexClusterNeiPixel;
                            currentPixel->numNeiPixelEachCluster[numNeiCluster-1]++;
                            *position = numNeiCluster - 1;
                    }
            }
            return counted;
    }

    /************************************************************************
    *Name of the function:  
    *				bool searchNei(struct pixel* pixelArray)
    *Parameter of the function
    *				pixelArray --- the array of pixels
    *Return Value: 
    *				0 fail, 1 successful
    *Comment: 
    *		search the neighbor pixels for every pixel, record the number of pixels
    *		inside each cluster
    ************************************************************************/
    bool searchNei(struct pixel* pixelArray){
            int numPixel = bmpWidth * bmpHeight;
            int neiIndex;
            int neiClusterIndex;
            int i,j;
            int position;
            for(i = 0; i < numPixel; i++){
                    for(j = 0; j < pixelArray[i].numNeiPixels;j++){
                            neiIndex = pixelArray[i].neiPixel[j];
                            if(neiIndex!=i){
                                    neiClusterIndex = pixelArray[neiIndex].indexCluster;
                                    isCounted(&pixelArray[i],neiClusterIndex,&position);
                            }
                    }
            }
            return true;
    }

    /************************************************************************
    *Name of the function:  
    *				bool isBoundaryPixel(struct pixel* currentPixel, struct pixel* pixelArray)
    *Parameter of the function:
    *				currentPixel --- the current pixel
    *Return Value: 
    *				0 not a boundary pixel, 1 yes
    *Comment: 
    *		tell if current pixel is a boundary pixel or not. boundary pixel
    *		means there is a direct neighbor pixel which is not belong to 
    *		the same cluster with currentPixel
    ************************************************************************/
    bool isBoundaryPixel(struct pixel* currentPixel, struct pixel* pixelArray){
            int i;
            int neiIndex;
            bool isOnBoundary = false;
            for(i = 0; i < currentPixel->numDirectNei; i++){
                    neiIndex = currentPixel->directNei[i];
                    if(currentPixel->indexCluster!=pixelArray[neiIndex].indexCluster){
                            isOnBoundary = true;
                            break;
                    }
            }
            return isOnBoundary;
    }

    /**********************************************************************************/
    /*  once a data transfer occurs, the index of cluster should be changed for this  */
    /*  data. In addtion the numNeiDataPerClusterp list of its neighbor points should */
    /*  be changed either                                                             */
    /**********************************************************************************/
    bool dataTransfer(struct pixel* currentPixel, int newIndex, struct pixel* pixelArray){
            int oldIndex = currentPixel->indexCluster;
            int i;
            int newIndexPosition;
//            int oldIndexPosition;
            bool oldIndexCounted = false;

            isCounted(currentPixel,newIndex,&newIndexPosition);

            for(i = 0; i < currentPixel->numNeiCluster; i++){
                    if(currentPixel->indexNeiClusters[i] == oldIndex){
                            currentPixel->numNeiPixelEachCluster[i]--;
//                            oldIndexPosition = i;
                            oldIndexCounted = true;
                            break;
                    }
            }

            if(oldIndexCounted == false){
                    printf("warning! can not find the cluster for the current pixel in the indexNeiClusters array!\n");
                    exit(0);
            }

            oldIndexCounted = false;
            int j;
            int indexNeiData;
            for(i = 0; i < currentPixel->numNeiPixels; i++){

                    indexNeiData = currentPixel->neiPixel[i];

                    if(indexNeiData!=currentPixel->index){

                            isCounted(&pixelArray[indexNeiData],newIndex,&newIndexPosition);

                                    for(j = 0; j < pixelArray[indexNeiData].numNeiCluster; j++){
                                            if(pixelArray[indexNeiData].indexNeiClusters[j] == oldIndex){
                                                    pixelArray[indexNeiData].numNeiPixelEachCluster[j]--;
//                                                    oldIndexPosition = j;
                                                    oldIndexCounted = true;
                                                    break;
                                            }
                                    }

                                    if(oldIndexCounted == false){
                                            printf("warning! can not find the cluster for the current pixel in the indexNeiClusters array!\n");
                                            exit(0);
                                    }
                    }
            }
                    currentPixel->indexCluster = newIndex;
                    return true;

            }

    /************************************************************************
    *Name of the function:  
    *				bool	classicCVT(struct centroid* generators, struct pixel* pixelArray)
    *Parameter of the function:
    *				generators --- the array of generators
    *				pixelArray --- the array of pixels
    *Return Value: 
    *				0 fail, 1 successful
    *Comment: 
    *		read a bmp image,
    *		First: segment the whole image by using CVT algorithm, only physical 
    *		space is considered.
    *		Second: adjust the segmentation according to the color information
    ************************************************************************/
    bool classicCVT(struct pixel* pixelArray, struct centroid* generators){

            VoronoiRegion(generators,pixelArray);
            searchNei(pixelArray);
            int i = 0;
            int numTransfer = bmpHeight * bmpWidth;
            int newNearestGenerator;
            int oldNearestGenerator;
            int step = 0;
            while(numTransfer >= THRESHOLD){
                    numTransfer = 0;
                    for(i = 0; i < bmpWidth * bmpHeight; i++){
                            if(isBoundaryPixel(&pixelArray[i], pixelArray)){
                                    newNearestGenerator = getNearestGenerator(generators,&pixelArray[i],1);
                                    oldNearestGenerator = pixelArray[i].indexCluster;
                                    if(newNearestGenerator!=oldNearestGenerator){
                                            dataTransfer(&pixelArray[i], newNearestGenerator, pixelArray);
                                            updateGenerator(&generators[newNearestGenerator], &pixelArray[i], 1);
                                            updateGenerator(&generators[oldNearestGenerator], &pixelArray[i], 0);
                                            numTransfer++;
                                    }
                            }
                    }
                    step++;
                    //printf("step %d    %d\n", step, numTransfer);
            }

            return true;

    }

    /**********************************************************************************/
    /*  get the EW distance from current pixel to specified cluster                   */                                                       
    /**********************************************************************************/
    double getEWDist(struct centroid* currentGenerator, struct pixel* currentPixel){
            double EWDist = 0;
            int i,j;
            int indexNeiCluster = currentGenerator->index;
            int currentCluster = currentPixel->indexCluster;

            for(i = 0; i < 3; i++){
                    EWDist += (currentGenerator->color[i] - currentPixel->color[i])*(currentGenerator->color[i] - currentPixel->color[i]);
            }

            for(j = 0; j < currentPixel->numNeiCluster; j++){
                    if(currentPixel->indexNeiClusters[j] == indexNeiCluster){
                            break;
                    }
            }

            if(currentCluster == indexNeiCluster){

                    EWDist += 2 * WEIGHT_LENGTH * (currentPixel->numNeiPixels - currentPixel->numNeiPixelEachCluster[j]);

            }else{
                    EWDist += 2 * WEIGHT_LENGTH * (currentPixel->numNeiPixels - currentPixel->numNeiPixelEachCluster[j]-1);
            }
            EWDist = sqrt(EWDist);
            return EWDist;
    }

    /**************************************************************************************/
    /*  get the index of cluster which is nearest to the current pixel in the  EW energy  */
    /*  sense                                                                             */                                                       
    /**************************************************************************************/
    int getShortestEWDist(struct centroid* generators, struct pixel* currentPixel){
            double shortestEWDist = 0.;
            double tempShortestEWDist = 0.;
//            int indexCluster;
            int indexCluster_shortestEWDist = currentPixel->indexCluster;
            int currentCluster = currentPixel->indexCluster;
            int indexNeiCluster;
            int i;

            shortestEWDist = getEWDist(&generators[currentCluster],currentPixel);
            for(i = 0; i < currentPixel->numNeiCluster; i++){
                    if(currentPixel->numNeiPixelEachCluster[i]!=0){
                            if(currentCluster!=currentPixel->indexNeiClusters[i]){
                                    indexNeiCluster = currentPixel->indexNeiClusters[i];
                                    tempShortestEWDist = getEWDist(&generators[indexNeiCluster],currentPixel);
                                    if(tempShortestEWDist < shortestEWDist){
                                            shortestEWDist = tempShortestEWDist;
                                            indexCluster_shortestEWDist = indexNeiCluster;
                                    }
                            }
                    }
            }
            return indexCluster_shortestEWDist;
    }

    /************************************************************************
    *Name of the function:  
    *				bool	EWCVT(struct centroid* generators, struct pixel* pixelArray)
    *Parameter of the function:
    *				generators --- the array of generators
    *				pixelArray --- the array of pixels
    *Return Value: 
    *				0 fail, 1 successful
    *Comment: 
    *		read a bmp image,
    *		segment the image by using the EWCVT algorithm
    ************************************************************************/
    bool EWCVT(struct centroid* generators, struct pixel* pixelArray){

            //printf("generating the EWCVT......\n");
            int i = 0;
            int numTransfer = bmpHeight * bmpWidth;
            int newNearestGenerator;
            int oldNearestGenerator;
            int step = 0;
            while(numTransfer >= THRESHOLD){
                    numTransfer = 0;
                    for(i = 0; i < bmpWidth * bmpHeight; i++){
                            if(isBoundaryPixel(&pixelArray[i], pixelArray)){
                                    newNearestGenerator = getShortestEWDist(generators,&pixelArray[i]);
                                    oldNearestGenerator = pixelArray[i].indexCluster;
                                    if(newNearestGenerator!=oldNearestGenerator){
                                            dataTransfer(&pixelArray[i], newNearestGenerator, pixelArray);
                                            updateGenerator(&generators[newNearestGenerator], &pixelArray[i], 1);
                                            updateGenerator(&generators[oldNearestGenerator], &pixelArray[i], 0);
                                            numTransfer++;
                                    }
                            }
                    }
                    step++;
                    //printf("step %d    %d\n", step, numTransfer);

            }

            return true;
    }
};

#endif	/* VCELLS_H */